# Implement regular expression matching with support for '.' and '*'.

# '.' Matches any single character.
# '*' Matches zero or more of the preceding element.

# The matching should cover the entire input string (not partial).

# The function prototype should be:
# bool isMatch(const char *s, const char *p)

# Some examples:
# isMatch("aa","a") → false
# isMatch("aa","aa") → true
# isMatch("aaa","aa") → false
# isMatch("aa", "a*") → true
# isMatch("aa", ".*") → true
# isMatch("ab", ".*") → true
# isMatch("aab", "c*a*b") → true

#wrong result ("aaa", "ab*a*c*a")
class Solution_1(object):
    def isEqual(self, sChar, pChar):
        return pChar == "." or sChar == pChar

    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

        i = 0
        j = 0

        while j < len(p):
            if i >= len(s):
                if j + 1 < len(p) and p[j + 1] == "*":
                    j += 2
                    continue
                else:
                    return False

            if self.isEqual(s[i], p[j]):
                i += 1
                j += 1
                continue

            if p[j] == "*":
                if self.isEqual(s[i], p[j-1]):
                    starChar = p[j-1]
                    iCount = 1
                    jCount = 0

                    while i < len(s):
                        if self.isEqual(s[i], starChar):
                            iCount += 1
                            i += 1
                        else:
                            break

                    j += 1
                    while j < len(p):
                        if p[j] == starChar:
                            jCount += 1
                            j += 1
                        else:
                            break

                    if iCount >= jCount:
                        continue
                    else:
                        return False

            if j + 1 < len(p) and p[j + 1] == "*":
                j += 2
                continue

            return False

        if i < len(s):
            return False

        return True


#
class Solution_2(object):
    def isEqual(self, s, p):
        i = 0
        while i < len(s):
            if s[i] != p[i] and p[i]

    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

        sLeft = ""
        sRight = ""
        pLeft = ""
        pRight = ""

        i = 0
        while i < len(p):
            if p[i] == "*":
                if i == 0 and s[i] != "*":
                    return False
                if i - 2 < 0:
                    break
                if i - 1 > len(s):
                    return False

                sLeft = s[:i-1]
                pLeft = p[:i-1]
                break

            i += 1

        i = len(p) - 1
        while i >= 0:
            if p[i] == "*":
                if i == 0 and s[i] != "*":
                    return False
                if i + 1 > len(p):
                    break
                if len(p) - i + 1 > len(s):
                    return False

                sRight = p[i+1:]
                pRight = p[i+1:]
                break

            i -= 1

        if pLeft != "" and (not self.isEqual(sLeft, pLeft)):
            return False
        if print != "" and (not self.isEqual(sRight, pRight)):
            return False

        



#test
solution = Solution_2()
result = solution.isMatch("aaa", "ab*a*c*a")

print("\n", "-----------------------------------------", "\n")
print(result)
print("\n", "-----------------------------------------", "\n")

